package Backtracking;

import java.util.ArrayList;
import java.util.List;

public class 复原IP地址 {

    List<String> res = new ArrayList<>();
    int len;
    String s;
    StringBuilder ip;

    public List<String> restoreIpAddresses(String s) {
        len = s.length();
        if (len > 12) return res;
        this.s = s;
        ip = new StringBuilder(s);
        backTracking(0, 1);
        return res;
    }

    private void backTracking(int index, int point) {
        if (point == 4) {
            if (index < len && isValid(s.substring(index))) res.add(ip.toString());
            return;
        }
        for (int i = index + 1; i <= Math.min(index + 3, len); i++) {
            String nums = s.substring(index, i);
            if (!isValid(nums)) continue;
            ip.insert(i + point - 1,'.');
            backTracking(i, point + 1);
            ip.deleteCharAt(i + point - 1);
        }
    }

    private boolean isValid(String s) {
        if (s.length() > 1 && s.charAt(0) == '0') return false;
        int num = Integer.parseInt(s);
        return num <= 255;
    }
}
